
#include <stdio.h>
#include <stdlib.h>
#include "modularity_mat.h"


int CreateModularityMat(sparse_matrix_lst* A, int* Group, int iGroupSize, elem*** ModMat_ptr, int** VertexDegrees_ptr, int* M)
{
    int iRow, i, j, iTemp = 0, iGroupIndex;
	cell_t *TempCell;
	cell_t **RowsTails, **ColsTails;

    (*VertexDegrees_ptr) = (int *)(calloc(iGroupSize, sizeof(int)));
	if ((*VertexDegrees_ptr) == NULL)
	{
		/*returning 0 to the calling function will free all dynamic memory before exiting*/
		return 0;
	}

	/*calculate each group vertex degree + total degrees of graph (M)*/

	(*M) = 0;  /*resetting total degrees counter*/
	iGroupIndex = 0;
	for (i=0; i<(A->n); i++)
	{
		/*pointing to the first non-zero cell in A in the i'th row*/
		TempCell = A->rows[i];

		if ((iGroupIndex < iGroupSize) && (i == Group[iGroupIndex]))   /*vertex i is in g*/
		{
			while(TempCell != NULL)
			{
				(*VertexDegrees_ptr)[iGroupIndex]++;   /*another vertex adjacent to i was found - increment i's degree*/
				(*M)++;
				TempCell = TempCell->row_next; 
			}
			iGroupIndex++;
		}
		else  /*vertex i is not in g*/
		{
			while(TempCell != NULL)
			{
				(*M)++;
				TempCell = TempCell->row_next; 
			}
		}
	}

	/* allocate B[g] matrix*/
	(*ModMat_ptr)= (elem **)(malloc(iGroupSize * sizeof(elem *)));
	
	if((*ModMat_ptr)== NULL)
	{
		puts(" Failure to allocate room for row pointers.");
		/*returning 0 to the calling function will free all dynamic memory before exiting*/
		return 0;
	}

	/* allocate B[g]'s rows*/
	for (iRow = 0; iRow < iGroupSize; iRow++)
	{
		(*ModMat_ptr)[iRow] = (elem *)malloc(iGroupSize * sizeof(elem));
		if ((*ModMat_ptr)[iRow] == NULL)
		{
			printf("Failure to allocate for row[%d]",iRow);
			/*returning 0 to the calling function will free all dynamic memory before exiting*/
			return 0;
		}
	}


	/*fill B[g] with values, according to formula (3)*/
	for (i=0; i<iGroupSize; i++)
	{
		/*pointing to the first non-zero cell in A in the i'th row*/
		TempCell = A->rows[Group[i]];

		for (j=0; j<iGroupSize; j++)             
		{
			while((TempCell != NULL) && (Group[j] > TempCell->colind))
			{
				TempCell = TempCell->row_next;
			}

			if ((TempCell != NULL) && (Group[j] == TempCell->colind))
			{
				(*ModMat_ptr)[i][j] = 1 - (elem)((elem)((*VertexDegrees_ptr)[i]*(*VertexDegrees_ptr)[j])/(*M));
				TempCell = TempCell->row_next; 
			}
			else
			{
				(*ModMat_ptr)[i][j] =  0 - (elem)((elem)((*VertexDegrees_ptr)[i]*(*VertexDegrees_ptr)[j])/(*M));  
			}
		}
	}

	return 1;
}


int CreateGeneralizedModMat(elem** B_g,int* Group,int iGroupSize, elem*** GnrModMat_ptr, elem** F_g_ptr)
{   
	int iRow, i, j, iCronekersDelta;
	elem dTemp;

    /* allocate the generalized modularity matrix B^[g]*/
    (*GnrModMat_ptr)= (elem **)(malloc(iGroupSize * sizeof(elem *)));
    /* allocating array to contain F_i(g):*/
    (*F_g_ptr) = (elem *)(calloc(iGroupSize, sizeof(elem)));

    if(((*GnrModMat_ptr)== NULL)||((*F_g_ptr) == NULL))
    {
        puts(" Failure to allocate room for row pointers.");
		return 0;
	}
    /* allocate the generalized modularity matrix's rows*/
    for (iRow = 0; iRow < iGroupSize; iRow++)
    {
        (*GnrModMat_ptr)[iRow] = (elem *)malloc(iGroupSize * sizeof(elem));
        if ((*GnrModMat_ptr)[iRow] == NULL)
        {
            printf("Failure to allocate for row[%d]",iRow);
            /*returning 0 to the calling function will free all dynamic memory before exiting*/
			return 0;
        }
    }

    /* calculate F_g[i]*/
    for (i=0; i<iGroupSize; i++)
    {
        dTemp=0;
        for (j=0; j<iGroupSize; j++)
        {
            dTemp += B_g[i][j];
        }

        (*F_g_ptr)[i] = dTemp;
    }

    /*fill in the generalized modularity matrix's elements, according to formula (9)*/
    for (i=0; i<iGroupSize; i++)
    {
        for (j=0; j<iGroupSize; j++) 
        {
            (i==j) ? (iCronekersDelta = 1) : (iCronekersDelta = 0) ;
            (*GnrModMat_ptr)[i][j] =  B_g[i][j] - iCronekersDelta*((*F_g_ptr)[i]);
        }
    }

	return 1;
}

int Free2dimensionalArray(elem **arr, int iLength)
{
    int iRow;

    for (iRow = 0; iRow < iLength; iRow++)
    {
		if (arr[iRow] != NULL)
		{
			free(arr[iRow]);
		}
    }
    free(arr);

	return 1;
}

int GetAgFromA(sparse_matrix_lst *A, sparse_matrix_lst** A_g_ptr, int *Group, int iGroupSize)
{
	int i,iGroupColIndex;
	cell_t* row_pointer, *CurrentCell, *tmp_cell;
	cell_t** GroupColsTails;

	(*A_g_ptr) = allocate_sparse_matrix_lst(iGroupSize);
	/* allocate iGroupSize column pointers, each points to last inserted cell in a specific column */
	GroupColsTails = (cell_t**)calloc(iGroupSize,sizeof(cell_t*));
	if (GroupColsTails == NULL)
	{
		FreeMem2(row_pointer,CurrentCell,tmp_cell,GroupColsTails, iGroupSize);
		return 0;
	}

	/* iterate over the rows in the sparse matrix A */
	for (i = 0; i < iGroupSize ; i++){
		/* iGroupColIndex is the lowest index in Group that we need to pass*/
		iGroupColIndex=0;
		CurrentCell = A->rows[Group[i]];
		while ((CurrentCell != NULL) && (iGroupColIndex < iGroupSize)){
			/*discard cell if it's index is still smaller than the group index*/
			if (CurrentCell->colind < Group[iGroupColIndex]){
				CurrentCell = CurrentCell->row_next;
				continue;
			}
			/*discard cell if it's index is larger than the group index 
			(means that A[curRow][CurrentCell->colind] was 0 to begin with)*/
			if (CurrentCell->colind > Group[iGroupColIndex]){
				iGroupColIndex++;
				continue;
			}
			/*if we got here,CurrentCell->colind = Group[iGroupColIndex], so we add it to A[g]*/
			tmp_cell = (cell_t*)malloc(sizeof(cell_t));

			if (tmp_cell == NULL)
			{
				/*returning 0 to calling function - it will safely exit by freeing allocated mem  */
				return 0;
			}

			/*fill in cell*/
			tmp_cell->value = CurrentCell->value;
			tmp_cell->col_next=NULL;
			tmp_cell->row_next=NULL;
			tmp_cell->colind=iGroupColIndex;
			tmp_cell->rowind=i;

			/* first cell starting a new row list */
			if ((*A_g_ptr)->rows[i] == NULL){
				(*A_g_ptr)->rows[i] = tmp_cell;
				row_pointer = (*A_g_ptr)->rows[i];
			}
			else{
				row_pointer->row_next = tmp_cell;
				row_pointer = row_pointer->row_next;
			}
			/* first cell starting a new column list*/
			if ((*A_g_ptr)->cols[iGroupColIndex] == NULL){
				(*A_g_ptr)->cols[iGroupColIndex] = tmp_cell;
				/*update col tail*/
				GroupColsTails[iGroupColIndex] = 
					(*A_g_ptr)->cols[iGroupColIndex];
			}
			else{
				GroupColsTails[iGroupColIndex]->col_next = tmp_cell;
				GroupColsTails[iGroupColIndex] = 
					GroupColsTails[iGroupColIndex]->col_next;
			}		

			/* advance to the next item in the original list in A*/
			CurrentCell = CurrentCell->row_next;
			iGroupColIndex++;
		}
	}

	/*freeing tails Array, we dont need it anymore*/
	free(GroupColsTails);

	return 1;
}

void FreeMem1(	elem **GnrModMat,elem **ModMat,int *GroupVertexDegrees, int *Group,elem* F_g, sparse_matrix_lst *A, sparse_matrix_lst *A_g, int iGroupSize)
{
	if (F_g != NULL){
		free(F_g);
	}
	if (GroupVertexDegrees != NULL){
		free(GroupVertexDegrees);
	}
	if (Group!= NULL){
		free(Group);
	}
	if (GnrModMat != NULL){
		Free2dimensionalArray(GnrModMat,iGroupSize);
	}
	if (ModMat!= NULL){
		Free2dimensionalArray(ModMat,iGroupSize);
	}
	if (A != NULL){
		free_sparse_matrix_lst(A);
	}
	if (A_g != NULL){
		free_sparse_matrix_lst(A_g);
	}
}

void FreeMem2(cell_t* row_pointer, cell_t* CurrentCell, cell_t* tmp_cell, cell_t** GroupColsTails, int iGroupSize)
{
	if (row_pointer != NULL){
		free(row_pointer);
	}
	if (CurrentCell != NULL){
		free(CurrentCell);
	}
	if (tmp_cell != NULL){
		free(tmp_cell);
	}
	if (GroupColsTails != NULL){
		free(GroupColsTails);
	}
}